We present an efficient algorithm for uniformly sampling from an arbitrary compact body $\mathcal{X} \subset \mathbb{R}^n$ from a warm start under isoperimetry and a natural volume growth condition. Our result provides a substantial common generalization of known results for convex bodies and star-shaped bodies. The complexity of the algorithm is polynomial in the dimension, the Poincaré constant of the uniform distribution on $\mathcal{X}$ and the volume growth constant of the set $\mathcal{X}$.

Return ˆ α We show the following generalization of Proposition 2.1. Moreover, Alg. 4 has sample complexity The sample complexity is clear so we focus on the first statement. Theorem 4.5 in [MU17]) on these events as i varies and noting that Hence recalling (A.2) above, we conclude that The other direction is similar. Using (A.2) in the same way as above, we find First we analyze the expected sample complexity. Finally Alg. 4 has sample complexity We do this using Bayes' rule.

We study pure exploration with infinitely many bandit arms generated i.i.d.

Regarding computational aspects of PML, [CSS19a] provided the first efficient algorithm with a non-trivialapproximation guarantee ofexp( n2/3logn),which further implied asample optimal universal estimator forn 1/6.